# Definition for a binary tree node.
# 尝试用栈求解这道题
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def hasPathSum(self, root, targetSum):
        if root==None:
            return False
        value=[]
        stack=[(root,0)]
        rest=targetSum
        while stack:
            tmp=stack.pop()
            while tmp[1]!=len(value):
                rest+=value.pop()
            # print("tmp: "+str(tmp),"value: "+str(value),"rest: "+str(rest))
            rest=rest-tmp[0].val
            value.append(tmp[0].val)
            if tmp[0].left:
                stack.append((tmp[0].left,tmp[1]+1))
            if tmp[0].right:
                stack.append((tmp[0].right,tmp[1]+1))
            if (not tmp[0].left) and (not tmp[0].right):
                if rest==0:
                    return True
        return False

def main():
    root=TreeNode(-2)
    root.left=TreeNode(-3)
    # root.left=TreeNode(4)
    # root.right=TreeNode(8)
    # root.left.left=TreeNode(11)
    # root.left.left.left=TreeNode(7)
    # root.left.left.right=TreeNode(2)
    # root.right.left=TreeNode(13)
    # root.right.right=TreeNode(4)
    # root.right.right.right=TreeNode(1)
    targetSum=-5
    sol=Solution()
    res=sol.hasPathSum(root,targetSum)
    print(res)

main()